﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;
// 贪心
//class Solution {
//public:
//    bool lemonadeChange(vector<int>& bills)
//    {
//        int five = 0, ten = 0;
//        for (int i = 0; i < bills.size(); i++)
//        {
//            if (bills[i] == 5)   five++;
//            else if (bills[i] == 10)
//            {
//                if (five == 0)   return false;
//                five--;
//                ten++;
//            }
//            else
//            {
//                if (five && ten)
//                {
//                    five--;
//                    ten--;
//                }
//                else if (five >= 3)    five -= 3;
//                else    return false;
//            }
//        }
//        return true;
//    }
//};
////动态规划
//class Solution
//{
//public:
//    int minPathSum(vector<vector<int>>& grid)
//    {
//        int m = grid.size(), n = grid[0].size();
//        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
//        dp[0][1] = dp[1][0] = 0;
//        for (int i = 1; i <= m; i++)
//            for (int j = 1; j <= n; j++)
//                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j -
//                1];
//        return dp[m][n];
//    }
//};

#include <string>
char& ToBigChar(char& ch)
{
    if (ch >= 'a' && ch <= 'z')
        ch = ch - 32;
    return ch;
}

//int main()
//{
//    string str, ret;
//    getline(cin, str);
//    for (int i = 0; i < str.size(); i++)
//    {
//        if (i == 0)
//            ret += ToBigChar(str[i]);
//        if (str[i] == ' ')
//        {
//            i++;
//            ret += ToBigChar(str[i]);
//        }
//    }
//    for (auto e : ret)   cout << e;
//    return 0;
//}

//int main()
//{
//    int n = 0;
//    cin >> n;
//    int sep = 0;
//    vector<int> dp(10);
//    dp[0] = 1; dp[1] = 1;
//    for (int i = 2; i < 10; i++)
//        dp[i] = dp[i - 1] + dp[i - 2];
//    int low = 0, top = 0;
//    for (int i = 0; i < 10; i++)
//    {
//        if (dp[i] >= n)
//        {
//            top = dp[i];
//            low = dp[i - 1];
//            break;
//        }
//    }
//    sep = min(top - n, n - low);
//    cout << sep;
//    return 0;
//}

// 单词搜索
//class Solution
//{
//    int dx[4] = { 1, -1, 0, 0 };
//    int dy[4] = { 0, 0, 1, -1 };
//    bool vis[7][7];
//
//    int m, n;
//public:
//    bool exist(vector<vector<char>>& board, string word)
//    {
//        m = board.size(), n = board[0].size();
//        for (int i = 0; i < m; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                if (board[i][j] == word[0])
//                {
//                    vis[i][j] = true;
//                    if (dfs(board, word, i, j, 1))  return true;
//                    vis[i][j] = false;
//                }
//            }
//        }
//        return false;
//    }
//    bool dfs(vector<vector<char>>& board, string& word, int i, int j, int pos)
//    {
//        if (pos == word.size())  return true;
//        for (int k = 0; k < 4; k++)
//        {
//            int x = i + dx[k], y = j + dy[k];
//            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == word[pos] && vis[x][y] == false)
//            {
//                vis[x][y] = true;
//                if (dfs(board, word, x, y, pos + 1)) return true;
//                vis[x][y] = false;
//            }
//        }
//        return false;
//    }
//};


class Solution
{
public:
    int uniquePaths(int m, int n)
    {
        // 动态规划
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        dp[1][1] = 1;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
            {
                if (i == 1 && j == 1) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        return dp[m][n];
        // 记忆化搜索
        // vector<vector<int>> memo(m + 1, vector<int>(n + 1));
        // return dfs(m, n, memo);
    }
    int dfs(int i, int j, vector<vector<int>>& memo)
    {
        if (memo[i][j] != 0)
        {
            return memo[i][j];
        }
        if (i == 0 || j == 0) return 0;
        if (i == 1 && j == 1)
        {
            memo[i][j] = 1;
            return 1;
        }
        memo[i][j] = dfs(i - 1, j, memo) + dfs(i, j - 1, memo);
        return memo[i][j];
    }
};

// dp
class Solution
{
public:
    int minCost(vector<vector<int>>& costs) {
        // dp[i][j] 第i个房⼦刷成第j种颜⾊最⼩花费
        int n = costs.size();
        vector<vector<int>> dp(n + 1, vector<int>(3));
        for (int i = 1; i <= n; i++) {
            dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i - 1][0];
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i - 1][1];
            dp[i][2] = min(dp[i - 1][1], dp[i - 1][0]) + costs[i - 1][2];
        }
        return min(dp[n][0], min(dp[n][1], dp[n][2]));
    }
};

class Solution
{
public:
    int maxProfit(vector<int>& prices)
    {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回结果
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(3));
        dp[0][0] = -prices[0];
        for (int i = 1; i < n; i++)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0] + prices[i];
        }
        return max(dp[n - 1][1], dp[n - 1][2]);
    }
};
// 全排列
class Solution
{
    vector<vector<int>> vv;
    vector<int> path;
    bool check[7];
public:
    vector<vector<int>> permute(vector<int>& nums)
    {
        dfs(nums);
        return vv;
    }
    void dfs(vector<int>& nums)
    {
        if (path.size() == nums.size())
        {
            vv.push_back(path);
            return;
        }
        for (int i = 0; i < nums.size(); i++)
        {
            if (check[i] == false)
            {
                path.push_back(nums[i]);
                check[i] = true;
                dfs(nums);
                path.pop_back();
                check[i] = false;
            }
        }
    }
};
// 递归、回溯
class Solution
{
    vector<vector<int>> vv;
    vector<int> path;
public:
    // 法一
    vector<vector<int>> subsets(vector<int>& nums)
    {
        dfs(nums, 0);
        return vv;
    }
    void dfs(vector<int>& nums, int x)
    {
        // 递归出口
        if (x == nums.size())
        {
            vv.push_back(path);
            return;
        }
        // 选
        path.push_back(nums[x]);
        dfs(nums, x + 1);
        path.pop_back();
        // 不选
        dfs(nums, x + 1);
    }
    // 法二
    /*vector<vector<int>> subsets(vector<int>& nums)
    {
        dfs(nums, 0);
        return vv;
    }
    void dfs(vector<int>& nums, int x)
    {
        vv.push_back(path);

        for (int i = x; i < nums.size(); i++)
        {
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
        }
    }*/
};


// 使用双向链表结构 + 哈希表
struct Node
{
    int _key, _val;
    Node* next, * prev;
    Node()
        :_key(0)
        , _val(0)
        , next(nullptr)
        , prev(nullptr)
    {}
    Node(int key, int val)
        :_key(key)
        , _val(val)
        , next(nullptr)
        , prev(nullptr)
    {}
};
#include <unordered_map>
// LRU缓存
class LRUCache
{
    Node* head, *tail;
    int _size;
    int _cap;
    unordered_map<int, Node*> hash;
public:
    LRUCache(int capacity)
        : _size(0)
        , _cap(capacity)
    {
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->prev = head;
    }
    int get(int key)
    {
        if (hash.count(key) == 0)    return -1;
        Node* node = hash[key];
        removeNode(node);
        addNodeToHead(node);
        return node->_val;
    }
    void put(int key, int value)
    {
        if (hash.count(key) != 0)
        {
            Node* node = hash[key];
            node->_val = value;
            removeNode(node);
            addNodeToHead(node);
        }
        else
        {
            if (_size == _cap)
            {
                Node* remove = tail->prev;
                removeNode(remove);
                hash.erase(remove->_key);
                _size--;
            }
            Node* node = new Node(key, value);
            addNodeToHead(node);
            hash[key] = node;
            _size++;
        }
    }
    // 移除当前结点
    void removeNode(Node* node)
    {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    // 将该节点插入到链表头
    void addNodeToHead(Node* node)
    {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
};

// K个一组反转链表
//class Solution {
//public:
//    ListNode* reverseKGroup(ListNode* head, int k)
//    {
//        if (head == nullptr || head->next == nullptr)    return head;
//        ListNode* cur = head;
//        int len = 0;
//        while (cur)
//        {
//            len++;
//            cur = cur->next;
//        }
//        cur = head;
//        int n = len / k;
//
//        ListNode* x = new ListNode(-1);
//        x->next = nullptr;
//        ListNode* prev = x;
//
//        for (int i = 0; i < n; i++)
//        {
//            ListNode* ret = cur;
//            for (int j = 0; j < k; j++)
//            {
//                ListNode* _next = cur->next;
//                cur->next = prev->next;
//                prev->next = cur;
//                cur = _next;
//            }
//            prev = ret;
//        }
//        prev->next = cur;
//        ListNode* ans = x->next;
//        delete x;
//        return ans;
//    }
//};
